package mao.leetcode.others.leetcode144;


import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        node1.right = node2;
       node2.left = node3;
        preorderTraversal(node1);
}

    public static List<Integer> preorderTraversal(TreeNode root) {

        List<Integer> l = new ArrayList<>();
        if (root == null) return l;   //注意判断空值
            Stack<ColoredTreeNode> s = new Stack<>();
        s.push(new ColoredTreeNode(root,true));
        while ( !s.isEmpty()){
            ColoredTreeNode node = s.pop();
            if (node.folded){
                if (node.node.right != null) s.push(new ColoredTreeNode(node.node.right,true));
                if (node.node.left != null) s.push(new ColoredTreeNode(node.node.left,true));
                node.folded = false;
                s.push(node);
            }else {
                l.add(node.node.val);
            }
        }
        return l;
    }

    public static class ColoredTreeNode  {
        boolean folded ;
        TreeNode node;
        ColoredTreeNode(TreeNode node,boolean folded){
            this.node = node;
            this.folded = folded;  //最好加上 this区分
        }
    }

    public static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
}
